package com.jp.algorithm.tree;

public class AVLTree {

    Node root;

    public AVLTree(){
        root = null;
    }

    private class Node{
        public int val;
        public Node left;
        public Node right;
        public int height=0;

        public Node(int val){
            this.val = val;
        }
    }

    public void insert(Node node){
        Node tmp = insertInner(root,node);
        root = tmp;
    }
    public Node insertInner(Node root,Node node){

        if(root  == null){
            return node;
        }
        else if(node.val < root.val){
            root.left = insertInner(root.left,node);
            if(height(root.left) - height(root.right) == 2){
                if(node.val < root.left.val){
                    adjustLL(root);
                }else{
                    adjustLR(root);
                }
            }
        }else{
            root.right = insertInner(root.right,node);
            if(height(root.right) - height(root.left) == 2){
                if(node.val > root.right.val){
                    adjustRR(root);
                }else{
                    adjustRL(root);
                }
            }
        }
        root.height = Math.max(height(root.left),height(root.right)) + 1;
        return root;
    }


    public Node deleteInner(Node root, int val){

        if(root.val == val){
            //叶子节点
            if(root.left == null && root.right == null){
                return null;
            }else if(root.left == null && root.right != null){
                return root.right;
            }else if(root.left == null && root.right != null){
                return root.left;
            }else{
                root.val = findMin(root.right);
                root.right = deleteInner(root.right,root.val);
            }
        }else if(root.val > val){
            root.left = deleteInner(root.left,val);
            if(height(root.right) - height(root.left) > 1){
                if(height(root.right.right) > height(root.right.left)){
                    adjustRR(root);
                }else{
                    adjustRL(root);
                }
            }
        }else{
            root.right = deleteInner(root.right,val);
            if(height(root.left) - height(root.right) > 1 ){
                if(height(root.left.left) > height(root.left.right)){
                    adjustLL(root);
                }else{
                    adjustLR(root);
                }
            }
        }
        root.height = Math.max(height(root.left),height(root.right)) + 1;
        return root;
    }
    public  int findMin(Node node){
        Node cur = node;
        while(cur.left != null){
            cur=cur.left;
        }
        return cur.val;
    }




    public  Node  adjustLL(Node k1){
        Node k2 = k1.left;

        k1.left = k2.right;
        k2.right = k1;
        k1.height = Math.max(height(k1.left),height(k1.right)) + 1;
        k2.height = Math.max(height(k2.left),k1.height) + 1;
        return k2;
    }
    public  Node  adjustRR(Node k1){
        Node k2 = k1.right;

        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max(height(k1.left),height(k1.right)) + 1;
        k2.height = Math.max(height(k2.left),k1.height) + 1;
        return k2;
    }
    public Node adjustRL(Node k1){
        k1.left = adjustLL(k1.left);
        return adjustRR(k1);
    }
    public Node adjustLR(Node k1){
        k1.right = adjustRR(k1.right);
        return adjustLL(k1);
    }




    public  int height(Node node){
        if(node  == null){
            return -1;
        }else{
            return node.height;
        }
    }
}
